package cn.mengfly.algorithm.sort;

import cn.mengfly.algorithm.util.ArrayUtil;

import java.util.Objects;

/**
 * @author Mengfly
 * @date 2021/4/11 13:17
 */
public class SortUtil {

    /**
     * 选择排序
     * <p>
     * 选择排序思想是：每次都找到未排序部分的最小值，放到已排序后的部分的后面
     */
    public static class Selection {
        public static <T extends Comparable<? super T>> void sort(T[] sort) {
            for (int i = 0; i < sort.length; i++) {
                int min = i;
                // 找到最小的元素的位置
                for (int j = i + 1; j < sort.length; j++) {
                    if (less(sort[j], sort[min])) {
                        min = j;
                    }
                }
                swap(sort, i, min);
            }
        }
    }

    /**
     * 插入排序
     * <p>
     * 对于某些非随机数组比较有效，对于一个很大但是比较接近有序的数组比选择排序要快
     * <p>
     * 最坏情况下：要排序的数组是逆序的，那么交换次数最多N^2/2
     * <p>
     * 插入排序的思想是：从未排序部分取出一个元素，放到已经排序的部分里面，由于已经排序的部分是有序的，所以放进去的时候比较方便。
     */
    public static class Insertion {
        public static <T extends Comparable<? super T>> void sort(T[] sort) {
            sort(sort, 0, sort.length - 1);
        }

        public static <T extends Comparable<? super T>> void sort(T[] sort, int lo, int hi) {
            for (int i = lo; i <= hi; i++) {
                T insertItem = sort[i];
                for (int j = i - 1; j >= 0; j--) {
                    // 如果这个值比比较的值小向后移动一位
                    if (less(insertItem, sort[j])) {
                        sort[j + 1] = sort[j];
                        // 边界
                        if (j == 0) {
                            sort[j] = insertItem;
                        }
                    } else {
                        sort[j + 1] = insertItem;
                        break;
                    }
                }
            }
        }
    }


    /**
     * 希尔排序
     * <p>
     * 希尔排序的思想：
     * 希尔排序是插入排序的进阶版，主要是利用了插入排序非常适合排序大体上是有序的数组
     * <p>
     * 希尔排序相当于在最后的插入排序之前，利用拆分数组的方式将数组粗略的排序。
     * <p>
     * 首先将整个数组按照 h 的步进长度切分数组，例如如果h=3的话，那么
     * 数组下标
     * <p>
     * {0,3,6,9...}是一组
     * {1,4,7,10 ...} 是一组
     * {2,5,8,11...} 是一组
     * <p>
     * 将这些子组分别进行排序，因此，可知在子组排序过程找那个，h越大，排序越快，因为h越大，每一个组里面的元素就越少
     * <p>
     * 所以，刚开始可以选择比较大的h进行粗略排序，然后慢慢缩小h，当h=1的时候，就是插入排序，但是经过之前的子组排序，
     * 整个数组已经排序的差不多了，再使用插入排序就会非常快
     */
    public static class Shell {
        public static <T extends Comparable<? super T>> void sort(T[] sort) {
            int n = sort.length;
            int h = 1;
            while (h < (n / 3)) {
                h = 3 * h + 1;
            }

            /*
             * 在h=1的时候，就是插入排序，但是这个时候，整个数组已经进行过了初步的排序
             * 所以使用插入排序的速度将会很快
             * 这里的代码逻辑为：后一组的值都要比前一组的值大
             * 从第h个数开始，和在它前h位的数比较，如果小就交换，否则跳出循环。交换了以后，继续和在它前h位的继续比较，一直到队首
             */
            while (h >= 1) {
                for (int i = h; i < n; i++) {
                    for (int j = i; j >= h && less(sort[j], sort[j - h]); j -= h) {
                        swap(sort, j, j - h);
                    }
                }
                h = h / 3;
            }
        }
    }

    /**
     * 归并排序
     */
    public static class Merge {

        private final Object[] auk;

        private Merge(int sortArrLength) {
            this.auk = new Object[sortArrLength];
        }

        public static <T extends Comparable<? super T>> void sort(T[] sort) {
            Merge merge = new Merge(sort.length);
            sort(merge, sort, 0, sort.length - 1);
        }

        private static <T extends Comparable<? super T>> void sort(Merge merge, T[] sort, int lo, int hi) {
            if (hi <= lo) {
                return;
            }
            int mid = lo + (hi - lo) / 2;
            // 左半边排序
            sort(merge, sort, lo, mid);
            // 右半边排序
            sort(merge, sort, mid + 1, hi);

            // 归并结果
            merge.merge(sort, lo, mid, hi);
        }


        @SuppressWarnings({"unchecked"})
        private <T extends Comparable<? super T>> void merge(T[] a, int lo, int mid, int hi) {
            int i = lo, j = mid + 1;

            System.arraycopy(a, lo, auk, lo, hi + 1 - lo);

            for (int k = lo; k <= hi; k++) {
                // 左半边已经读取完了
                if (i > mid) {
                    a[k] = (T) auk[j++];
                } else if (j > hi) {
                    // 右半边已经读取完了
                    a[k] = (T) auk[i++];
                } else if (less((T) auk[j], (T) auk[i])) {
                    // 右半边的值比较小
                    a[k] = (T) auk[j++];
                } else {
                    // 左半边的值比较小
                    a[k] = (T) auk[i++];
                }
            }
        }
    }

    /**
     * 自底向上的归并排序算法
     * <p>
     * 首先两两归并（这时候每两个一组的元素都是有序的）
     * <p>
     * 然后四四归并（这时候每四个一组的元素都是有序的）
     * <p>
     * ......
     * <p>
     * 这种排序方式非常适合链表数据，因为这是一种顺序的循序渐进的排序方式，如果是链表数据的话，只需要重新组织链表就可以将链表原地排序
     */
    public static class MergeBu {

        public static <T extends Comparable<? super T>> void sort(T[] sort) {
            int length = sort.length;
            Merge bu = new Merge(length);
            // sz is 1,2,4,8,16...
            for (int sz = 1; sz < length; sz += sz) {
                for (int lo = 0; lo < length - sz; lo += (sz + sz)) {
                    bu.merge(sort, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, length - 1));
                }
            }
        }
    }

    /**
     * 快速排序
     * <p>
     * 快速排序和归并排序都是利用的分治的思想，不同的是：快速排序是原地排序，节省了空间
     * <p>
     * 另外，归并排序的思想是，将数组分为两个部分，如果这两个部分都是有序的话，将他们归并为一个大数组
     * 具体的归并排序逻辑是在递归后进行的
     * <p>
     * 而快速排序不同，快速排序的基本逻辑是在递归之前的，它的思想是：将一个数组以一个分界线分为两个部分，
     * 如果这两个部分都是有序的话那整个数组就是有序的了
     * <p>
     * 可以看到，归并排序和快速排序的具体逻辑的不同在于一个是不断归并一个是不断拆分：
     * 1. 归并排序通过归并两个有序数组达到排序的目的
     * <p>
     * 2.快速排序是通过拆分数组为两个有序数组达到排序的目的
     */
    public static class Quick {
        /**
         * 在处理小数组排序的时候，插入排序要比快速排序有效，因此这里设置一个值，小于这个值的可以认为是小数组，使用插入排序
         */
        public static final int INSERTION_SORT_COUNT = 8;

        public static <T extends Comparable<? super T>> void sort(T[] sort) {
            ArrayUtil.shuffle(sort);
            sort(sort, 0, sort.length - 1);
        }

        private static <T extends Comparable<? super T>> void sort(T[] sort, int lo, int hi) {
            if (hi <= lo + INSERTION_SORT_COUNT) {
                Insertion.sort(sort, lo, hi);
                return;
            }
            // 切分
            int j = partition(sort, lo, hi);
            sort(sort, lo, j - 1);
            sort(sort, j + 1, hi);
        }

        /**
         * 以数组中的某个数为基准将数据拆分为两个部分，左边的部分都比这个数小，右边的都比这个数大，并将这个数在数组中的最终位置返回
         *
         * @param sort 要拆分的数组
         * @param lo   要拆分的起始位置
         * @param hi   要拆分的结束位置
         * @return 基准数所在数组中的位置
         */
        private static <T extends Comparable<? super T>> int partition(T[] sort, int lo, int hi) {
            int i = lo, j = hi + 1;
            T t = sort[lo];
            while (true) {
                // 找到左边的比t大的值的位置
                while (less(sort[++i], t)) {
                    if (i == hi) {
                        break;
                    }
                }
                // 找到右边的比t小的值的位置
                //noinspection StatementWithEmptyBody
                while (less(t, sort[--j])) {
                }
                // 如果左边位置比右边都大的话，就没有交换的必要了
                if (i >= j) {
                    break;
                }
                swap(sort, i, j);
            }
            // 将基准值放在正确的位置
            swap(sort, lo, j);
            return j;
        }
    }

    /**
     * 三向切分的快速排序
     * <p>
     * 具体思想是将数组分为三个部分：小于，等于和大于
     */
    public static class Quick3Way {
        public static <T extends Comparable<? super T>> void sort(T[] sort) {
            ArrayUtil.shuffle(sort);
            sort(sort, 0, sort.length - 1);
        }

        private static <T extends Comparable<? super T>> void sort(T[] sort, int lo, int hi) {
            if (hi <= lo) {
                return;
            }
            // 这里最终结束的时候，lt和gt标识的位置都是t的位置
            // 首先，i的位置的前面一个元素的值一定是t，因为被i扫过的区域已经归好类了，在i的前面不可能出现比t大的值
            int lt = lo, i = lo + 1, gt = hi;

            T t = sort[lo];
            while (i <= gt) {
                int cmp = sort[i].compareTo(t);
                if (cmp < 0) {
                    swap(sort, lt++, i++);
                } else if (cmp > 0) {
                    swap(sort, i, gt--);
                } else {
                    i++;
                }
            }
            sort(sort, lo, lt - 1);
            sort(sort, gt + 1, hi);
        }
    }

    /**
     * 判断t1是否小于t2
     *
     * @param t1 t1
     * @param t2 t2
     * @return t1小于t2的时候返回true
     */
    public static <T extends Comparable<? super T>> boolean less(T t1, T t2) {
        return t1.compareTo(t2) < 0;
    }

    /**
     * 交换数组两个位置的对象
     *
     * @param arr 数组
     * @param i   要交换的第一个位置
     * @param j   要交换的第二个位置
     */
    public static <T> void swap(T[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 判断数组是否是已经排序过的
     *
     * @param arr 数组
     * @return 已经排序过的返回True
     */
    public static <T extends Comparable<? super T>> boolean isSorted(T[] arr) {
        Boolean isDesc = null;

        for (int i = 1; i < arr.length; i++) {
            if (Objects.equals(arr[i], arr[i - 1])) {
                continue;
            }

            boolean isLess = less(arr[i], arr[i - 1]);
            if (isDesc == null) {
                isDesc = isLess;
            } else {
                if (isLess != isDesc) {
                    return false;
                }
            }
        }
        return true;
    }


}
